//
//  707. 设计链表.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/7/14.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
// 这个链表的在指定的位置添加元素。
// 有两种情况:1. 是有头结点 2. 没有头节点
// 删除元素时也有两种情况
// 1. 删除头节点 2. 删除非头节点
class MyLinkedList {
    var virtual: ListNode = ListNode(-1)
    // 获取链表中第index个节点的值
    func get(_ index: Int) -> Int {
        var i = 0
        var p = virtual.next
        while p != nil {
            if i == index {
                if let p = p {
                    return p.val
                }
            }
            p = p?.next
            i += 1
        }
        return -1
    }
    // 在链表的第一个元素之前添加一个值为val的节点(采用虚拟节点)
    func addAtHead(_ val: Int) {
        let head = virtual.next
        let node = ListNode(val)
        virtual.next = node
        node.next = head
    }
    // 将val追加到链表的最后一个元素
    func addAtTail(_ val: Int) {
        var p: ListNode? = virtual
        while p?.next != nil {
            p = p?.next
        }
        p?.next = ListNode(val)
    }
    func addAtIndex(_ index: Int, _ val: Int) {
        var i = 0
        var last: ListNode? = virtual
        var p: ListNode? = virtual.next
        // 找到那个节点，放在last的后面
        while p != nil {
            if i == index {
                if let p = p {
                    let node = ListNode(val)
                    last?.next = node
                    node.next = p
                }
            }
            last = p
            p = p?.next
            i += 1
        }
        // 恰好在最后
        if index == i {
            last?.next = ListNode(val)
        }
    }
    // 删除时，用一个节点记录上一个节点
    func deleteAtIndex(_ index: Int) {
        var i = 0
        var last: ListNode? = virtual
        var p: ListNode? = virtual.next
        while p != nil {
            if i == index {
                last?.next = p?.next
            }
            last = p
            p = p?.next
            i += 1
        }
    }
}

class Solution707 {
    static func test() {
        let linkedList = MyLinkedList()
        
        linkedList.addAtIndex(0, 10)
        
        linkedList.addAtIndex(0, 20)
        
        linkedList.addAtIndex(1, 30)
        
    }
}
